Random order в Postgres

Случайность — маска неузнанной закономерности
Александр Волков

Как-то я писал о том как быстро можно сделать выборку в MySQL по большой таблице в случайном порядке не используя ORDER BY RAND(), теперь этот же вопрос всплыл на Postgre. Если вы не знаете, то ORDER BY RAND достаточно медленная операция из-за того, что сортируется фактически вся таблица. Некоторые советовали всё-таки обычную сортировку или чуть-изменённую с использованием Primary Key, но я на своём опыте убедился что конструкция IN всегда медленней чем EXISTS.

Электроны и дырки

Вообще задача подразумевает выборку и нескольких случайных рядов, но она сводится к выборке одного ряда, а точней ID. Самый простой способ - взять минимум (MIN или 1), максимум (MAX или значение Sequence) и случайным образом тыкнуть в промежутке. Задача чем-то напоминает процесс хэширования. И всё хорошо покуда всё идёт по порядку и ряды не удаляются. Как только в базе возникают пустоты (а они возникают вероятностью пропорционально размеру проекта), то получается что ряд не находится.

Использовать наиболее близкий к этой дырке ID'шник мы не можем из-за неравномерного распределения вероятностей и не гарантированного присутсвия вообще каких-то данных если мы в конце. Хотя можно плюнуть..

SELECT * FROM mytable WHERE id >= CEIL(RANDOM()*(SELECT MAX() FROM mytable)) ORDER BY id LIMIT 1;

Лотерея

Делать цикл с простукиванием каждой дыры тоже рискованно - вставит кто-нибудь гипер прыжок ID с 435 на 43600 и сложность алгоритма прыгнет основательно. 

Можно оторваться от ID'шек и внести случайны float-параметр. Такой лотерее дыры в ID уже неважны. Но  неравномерность вероятности всё-таки существует и в таком случае. Правда чем больше рядов, тем она незначительней, но тем больше места занимают эти лишние данные.

ALTER TABLE mytable ADD myrand DOUBLE PRECISION; --добавляем колонку UPDATE mytable SET myrand = RANDOM(); --очень медленная процедура ALTER TABLE mytable ALTER myrand SET NOT NULL DEFAULT RANDOM(); --ставим случайное значение для новых рядов по умолчанию SELECT * FROM mytable WHERE myrand >= (SELECT RANDOM() OFFSET 0) ORDER BY myrand ASC LIMIT 1;

Горст и грабен

Ещё простое решение - использовать случайный OFFSET. Сразу минус - LIMIT конструкция не позволяет динамически задавать значения, но образно идея такая:

SELECT CEIL(RANDOM()*(SELECT COUNT(*) AS cnt FROM mytable)); --получим из базы offset SELECT * FROM quotes LIMIT 1 OFFSET 43600; --и передадим в явном виде в запрос

LIMIT сразу перейдёт к нужному ряду - нет нужды в ID, а значит больше свободы. Единственный вопрос в скорости. Ведь используемая внутри COUNT функция - аггрегирующая, а в Postgre она отличается от обычного счётчика в MySQL. Ко всему прочему, как говорит документация - OFFSET может быть неэффективным в больших базах из-за того, что обработка предыдущих рядов всё-равно происходит.